﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace Othello
{
    [Serializable]
    public class BoardStep
    {
        public Board Board { get; set; }
        public int Score { get; set; }
        public int Point { get; set; }
    }



    public static class OthelloUtil
    {
        public class BoardComparer : IComparer<BoardStep>
        {
            public int Compare(BoardStep x, BoardStep y)
            {
                return (int)(y.Score - x.Score);
            }
        }

        public const UInt64 HorizonFlag = 0xffL;
        public const UInt64 VerticalFlag = 0x0101010101010101L;
        public const UInt64 LeftSlantFlag = 0x8040201008040201L;
        public const UInt64 RightSlantFlag = 0x0102040810204080L;
        public const int MaxSearchDepth = 18;
        public const int MaxMoveableCount = 28;
        public static int SearchDepth = 7;

        private static int[] pointCounts = new int[256];
        private static Dictionary<UInt64, byte> rowMaps = new Dictionary<UInt64, byte>();
        private static Dictionary<byte, UInt64> verticalMaps = new Dictionary<byte, UInt64>();
        private static Dictionary<byte, UInt64> leftSlantMaps = new Dictionary<byte, UInt64>();
        private static Dictionary<byte, UInt64> rightSlantMaps = new Dictionary<byte, UInt64>();

        private static IComparer<BoardStep> comparer = new BoardComparer();
        private static BoardStep[][] boardStepPool = new BoardStep[MaxSearchDepth][];
        private static SortedDictionary<ushort, int> rowScores = new SortedDictionary<ushort, int>();
        private static Dictionary<ushort, byte> moveablePointsCache = new Dictionary<ushort, byte>(0x40ff);
        private static Dictionary<BoardStruct, int> scoreLibary = new Dictionary<BoardStruct, int>();
        private static Dictionary<BoardStruct, int> preLibary = new Dictionary<BoardStruct, int>();
        private static int calCount = 0;
        private const UInt64 CornerFlag = 0x8100000000000081L;
        private const UInt64 InCornerFlag = 0x0042000000004200L;

        static OthelloUtil()
        {
            for (int i = 0; i < 256; i++)
            {
                UInt64 vertical = 0;
                UInt64 leftSlant = 0;
                UInt64 rightSlant = 0;
                byte horizontal = (byte)i;
                pointCounts[i] = 0;
                for (int j = 7; j >= 0; j--)
                {
                    leftSlant <<= Board.Size + 1;
                    vertical <<= Board.Size;
                    rightSlant <<= Board.Size - 1;
                    if ((horizontal >> j & 1) == 1) { pointCounts[i]++; leftSlant |= 1; rightSlant |= 1; vertical |= 1; }
                }
                rightSlant <<= 7;
                rowMaps[vertical] = (byte)i;
                rowMaps[leftSlant] = (byte)i;
                rowMaps[rightSlant] = (byte)i;
                verticalMaps[(byte)i] = vertical;
                leftSlantMaps[(byte)i] = leftSlant;
                rightSlantMaps[(byte)i] = rightSlant;
            }
            for (int i = 0; i < MaxSearchDepth; i++)
            {
                boardStepPool[i] = new BoardStep[MaxMoveableCount];
                for (int j = 0; j < MaxMoveableCount; j++)
                {
                    boardStepPool[i][j] = new BoardStep() { Board = new Board() };
                }
            }
        }

        public static int CountBit(UInt64 nValue)
        {
            return pointCounts[(byte)nValue] + pointCounts[(byte)(nValue >> 8)] + pointCounts[(byte)(nValue >> 16)] + pointCounts[(byte)(nValue >> 24)]
                + pointCounts[(byte)(nValue >> 32)] + pointCounts[(byte)(nValue >> 40)] + pointCounts[(byte)(nValue >> 48)] + pointCounts[(byte)(nValue >> 56)];
        }

        public static BoardStep SeachForNextStep(Board board)
        {
            List<BoardStep> boardMaps = new List<BoardStep>();
            for (int i = 0; i < board.MoveableCount; i++)
            {
                Board temp = board.Clone();
                temp.PutDown(board.MoveablePoints[i] / Board.Size, board.MoveablePoints[i] % Board.Size);
                BoardStep boardMap = new BoardStep()
                {
                    Board = temp,
                    Point = board.MoveablePoints[i],
                    Score = -GetScore(temp)
                };
                boardMaps.Add(boardMap);
            }

            boardMaps.Sort(comparer);

            int alpha = -0xffffff;
            int beta;
            int depth;
            if (board.SelfCount + board.OtherCount > 48)
            {
                beta = 1000;
                depth = MaxSearchDepth;
            }
            else if (board.SelfCount + board.OtherCount > 52)
            {
                beta = 0xffffff;
                depth = MaxSearchDepth;
            }
            else
            {
                beta = 100;
                depth = SearchDepth;
            }

            BoardStep candidate = null;
            preLibary = scoreLibary;
            scoreLibary = new Dictionary<BoardStruct, int>(20000);
            calCount = 0;
            DateTime time = DateTime.Now;

            for (int i = 0; i < boardMaps.Count; i++)
            {
                int score = -AlphaBeta(boardMaps[i].Board, depth, 0, -beta, -alpha);
                boardMaps[i].Score = score;
                if (score > alpha)
                {
                    alpha = score;
                    candidate = boardMaps[i];
                }
            }
            tw.Flush();
            Console.WriteLine("{0},{1} {2}", alpha, calCount, DateTime.Now - time);
            return candidate;
        }

        private static void AddLibrary(Board board, int score)
        {
            scoreLibary[new BoardStruct(board.SelfRows, board.OtherRows)] = score;
        }

        public static int AlphaBeta(Board board, int maxDepth, int depth, int alpha, int beta)
        {
            calCount++;
            if (scoreLibary.ContainsKey(board.board))
                return scoreLibary[board.board];
            else if (board.Finished || depth >= maxDepth)
            {
                return GetScore(board);
            }
            else if (board.MoveableCount == 0)
            {
                board.Reverse();
                return -AlphaBeta(board, maxDepth, depth, -beta, -alpha);
            }

            BoardStep[] boardMaps = boardStepPool[depth];

            for (int i = 0; i < board.MoveableCount; i++)
            {
                boardMaps[i].Board.CopyFrom(board);
                boardMaps[i].Board.PutDown(board.MoveablePoints[i] / Board.Size, board.MoveablePoints[i] % Board.Size);
                boardMaps[i].Point = board.MoveablePoints[i];
                boardMaps[i].Score = -GetScore(boardMaps[i].Board);
            }

            Array.Sort(boardStepPool[depth], 0, board.MoveableCount, comparer);
            if (depth == maxDepth - 1) return Math.Min(boardStepPool[depth][0].Score, beta);

            for (int i = 0; i < board.MoveableCount; i++)
            {
                int score = -AlphaBeta(boardMaps[i].Board, maxDepth, depth + 1, -beta, -alpha);
                if (score >= beta)
                {
                    AddLibrary(board, beta);
                    return beta;
                }
                if (score > alpha)
                {
                    alpha = score;
                }
            }
            AddLibrary(board, beta);
            return alpha;
        }

        public static byte GetMoveablePlaces(byte self, byte other)
        {
            ushort row = (ushort)((other << 8) | self);
            if (moveablePointsCache.ContainsKey(row)) return moveablePointsCache[row];
            byte currentPlaces = (byte)(self | other);
            byte emptyPlaces = (byte)~currentPlaces;
            int mixPlaces = self;
            for (int i = 0; i < Board.Size; i++)
            {
                mixPlaces |= (mixPlaces << 1 & other) | (mixPlaces >> 1 & other);
            }
            int otherMixPlaces = other & mixPlaces;
            int moveablePlaces = (otherMixPlaces << 1 | otherMixPlaces >> 1) & emptyPlaces;
            moveablePointsCache[row] = (byte)moveablePlaces;
            return (byte)moveablePlaces;
        }

        public static UInt64 GetMoveablePlaces(UInt64 selfRows, UInt64 otherRows)
        {
            UInt64 moveableRows = 0;
            byte self, other, m;
            for (int i = 0; i < Board.Size; i++)
            {
                self = (byte)(selfRows >> (i * Board.Size));
                other = (byte)(otherRows >> (i * Board.Size));
                m = OthelloUtil.GetMoveablePlaces(self, other);
                moveableRows |= ((UInt64)m) << (i * Board.Size);

                self = rowMaps[selfRows >> i & VerticalFlag];
                other = rowMaps[otherRows >> i & VerticalFlag];
                m = OthelloUtil.GetMoveablePlaces(self, other);
                moveableRows |= verticalMaps[m] << i;
            }

            self = rowMaps[selfRows & LeftSlantFlag];
            other = rowMaps[otherRows & LeftSlantFlag];
            m = OthelloUtil.GetMoveablePlaces(self, other);
            moveableRows |= leftSlantMaps[m];

            self = rowMaps[selfRows & RightSlantFlag];
            other = rowMaps[otherRows & RightSlantFlag];
            m = OthelloUtil.GetMoveablePlaces(self, other);
            moveableRows |= rightSlantMaps[m];

            for (int i = 1; i < 6; i++)
            {
                self = rowMaps[selfRows >> (i * Board.Size) & LeftSlantFlag];
                other = rowMaps[otherRows >> (i * Board.Size) & LeftSlantFlag];
                m = OthelloUtil.GetMoveablePlaces(self, other);
                moveableRows |= leftSlantMaps[m] << (i * Board.Size);

                self = rowMaps[selfRows >> (i * Board.Size) & RightSlantFlag];
                other = rowMaps[otherRows >> (i * Board.Size) & RightSlantFlag];
                m = OthelloUtil.GetMoveablePlaces(self, other);
                moveableRows |= rightSlantMaps[m] << (i * Board.Size);

                self = rowMaps[selfRows << (i * Board.Size) & LeftSlantFlag];
                other = rowMaps[otherRows << (i * Board.Size) & LeftSlantFlag];
                m = OthelloUtil.GetMoveablePlaces(self, other);
                moveableRows |= leftSlantMaps[m] >> (i * Board.Size);

                self = rowMaps[selfRows << (i * Board.Size) & RightSlantFlag];
                other = rowMaps[otherRows << (i * Board.Size) & RightSlantFlag];
                m = OthelloUtil.GetMoveablePlaces(self, other);
                moveableRows |= rightSlantMaps[m] >> (i * Board.Size);
            }
            return moveableRows;
        }

        public static void PutDown(ref BoardStruct board, int row, int column)
        {
            UInt64 s = 0;
            UInt64 selfRows = board.SelfRows;
            UInt64 otherRows = board.OtherRows;
            byte self = (byte)(selfRows >> (row * Board.Size));
            byte other = (byte)(otherRows >> (row * Board.Size));
            PutDown(ref self, ref other, column);
            s |= (UInt64)self << (row * Board.Size);

            self = rowMaps[selfRows >> column & VerticalFlag];
            other = rowMaps[otherRows >> column & VerticalFlag];
            PutDown(ref self, ref other, row);
            s |= verticalMaps[self] << column;

            int distance = (row - column) * Board.Size;

            if (distance >= 0)
            {
                self = rowMaps[selfRows >> distance & LeftSlantFlag];
                other = rowMaps[otherRows >> distance & LeftSlantFlag];
                PutDown(ref self, ref other, column);
                s |= leftSlantMaps[self] << distance;
            }
            else
            {
                self = rowMaps[selfRows << -distance & LeftSlantFlag];
                other = rowMaps[otherRows << -distance & LeftSlantFlag];
                PutDown(ref self, ref other, column);
                s |= leftSlantMaps[self] >> -distance;
            }

            distance = (row + column - 7) * Board.Size;
            if (distance >= 0)
            {
                self = rowMaps[selfRows >> distance & RightSlantFlag];
                other = rowMaps[otherRows >> distance & RightSlantFlag];
                PutDown(ref self, ref other, 7 - column);
                s |= rightSlantMaps[self] << distance;
            }
            else
            {
                self = rowMaps[selfRows << -distance & RightSlantFlag];
                other = rowMaps[otherRows << -distance & RightSlantFlag];
                PutDown(ref self, ref other, 7 - column);
                s |= rightSlantMaps[self] >> -distance;
            }

            board.SelfRows |= s;
            board.OtherRows &= ~s;
        }

        public static void PutDown(ref byte self, ref byte other, int place)
        {
            int mixPlaces = self;
            for (int i = 0; i < Board.Size; i++)
            {
                mixPlaces |= (mixPlaces << 1 & other) | (mixPlaces >> 1 & other);
            }
            int otherMixPlaces = other & mixPlaces;
            int reversePlaces = 1 << place;
            for (int i = 0; i < Board.Size; i++)
            {
                reversePlaces |= (reversePlaces << 1 & otherMixPlaces) | (reversePlaces >> 1 & otherMixPlaces);
            }
            self |= (byte)reversePlaces;
            other &= (byte)~reversePlaces;
        }

        public static int GetScore(Board board)
        {
            if (board.Finished)
            {
                return (board.SelfCount - board.OtherCount) * 1000;
            }
            else
            {
                BoardStruct s = new BoardStruct(board.SelfRows, board.OtherRows);
                if (scoreLibary.ContainsKey(board.board))
                    return scoreLibary[board.board];
                else if (preLibary.ContainsKey(board.board))
                    return preLibary[board.board];
                else
                {
                    UInt64 selfRows = board.SelfRows;
                    UInt64 otherRows = board.OtherRows;
                    UInt64 emptyRows = ~(selfRows | otherRows);
                    UInt64 edgeRows = 0x007e7e7e7e7e7e00L & (emptyRows >> 1 | emptyRows << 1 | emptyRows >> 8 | emptyRows << 8 | emptyRows >> 7 | emptyRows << 7 | emptyRows >> 9 | emptyRows << 9);
                    UInt64 selfEdgeRows = 0x007e7e7e7e7e7e00L & selfRows;
                    selfEdgeRows = emptyRows & (selfEdgeRows >> 1 | selfEdgeRows << 1 | selfEdgeRows >> 8 | selfEdgeRows << 8 | selfEdgeRows >> 7 | selfEdgeRows << 7 | selfEdgeRows >> 9 | selfEdgeRows << 9);
                    UInt64 otherEdgeRows = 0x007e7e7e7e7e7e00L & otherRows;
                    otherEdgeRows = emptyRows & (otherEdgeRows >> 1 | otherEdgeRows << 1 | otherEdgeRows >> 8 | otherEdgeRows << 8 | otherEdgeRows >> 7 | otherEdgeRows << 7 | otherEdgeRows >> 9 | otherEdgeRows << 9);
                    UInt64 moveableRows = board.moveableRows;
                    UInt64 otherMoveableRows = board.otherMoveableRows;
                    int sideScore = (CountBit(otherEdgeRows & CornerFlag) - CountBit(selfEdgeRows & CornerFlag)) * 32
                        + (CountBit(otherMoveableRows & InCornerFlag) - CountBit(moveableRows & InCornerFlag)) * 2
                        + (pointCounts[otherRows & 0x81] + pointCounts[otherRows >> 56 & 0x81] - pointCounts[selfRows & 0x81] - pointCounts[selfRows >> 56 & 0x81]) * 64
                        + (GetScore((byte)selfRows, (byte)otherRows) + GetScore((byte)(selfRows >> 56), (byte)(otherRows >> 56)) + GetScore(rowMaps[selfRows & VerticalFlag], rowMaps[otherRows & VerticalFlag]) + GetScore(rowMaps[selfRows >> 7 & VerticalFlag], rowMaps[otherRows >> 7 & VerticalFlag]));
                    sideScore = sideScore * (CountBit(emptyRows) + 8) / 128;
                    return (board.MoveableCount - board.OtherMoveableCount + CountBit(otherEdgeRows) - CountBit(selfEdgeRows) + (CountBit(edgeRows & otherRows) - CountBit(edgeRows & selfRows)) * 2 + sideScore) / 4;
                }
            }
        }


        public static int GetScore(byte self, byte other)
        {
            ushort row = (ushort)(other << 8 | self);
            if (rowScores.ContainsKey(row)) return (int)rowScores[row];
            else
            {
                int score = CalScore(self, other);
                rowScores[row] = score;
                return (int)score;
            }
        }

        public static void Save()
        {
            StreamWriter tw = new StreamWriter("2.txt");
            foreach (KeyValuePair<ushort, int> rowScore in rowScores)
            {
                ushort row = rowScore.Key;
                tw.Write(Convert.ToString(row, 2).PadLeft(16, '0') + " ");
                for (int i = 0; i < 8; i++)
                {
                    if ((row >> i & 1) == 1) tw.Write("O");
                    else if ((row >> 8 >> i & 1) == 1) tw.Write("X");
                    else tw.Write("_");
                }
                tw.WriteLine(" " + rowScore.Value);
            }
            tw.Flush();
        }

        public static void SaveScore(Board board)
        {
            UInt64 selfRows = board.SelfRows;
            UInt64 otherRows = board.OtherRows;
            UInt64 emptyRows = ~(selfRows | otherRows);
            UInt64 edgeRows = 0x007e7e7e7e7e7e00L & (emptyRows >> 1 | emptyRows << 1 | emptyRows >> 8 | emptyRows << 8 | emptyRows >> 7 | emptyRows << 7 | emptyRows >> 9 | emptyRows << 9);
            UInt64 selfEdgeRows = 0x007e7e7e7e7e7e00L & selfRows;
            selfEdgeRows = emptyRows & (selfEdgeRows >> 1 | selfEdgeRows << 1 | selfEdgeRows >> 8 | selfEdgeRows << 8 | selfEdgeRows >> 7 | selfEdgeRows << 7 | selfEdgeRows >> 9 | selfEdgeRows << 9);
            UInt64 otherEdgeRows = 0x007e7e7e7e7e7e00L & otherRows;
            otherEdgeRows = emptyRows & (otherEdgeRows >> 1 | otherEdgeRows << 1 | otherEdgeRows >> 8 | otherEdgeRows << 8 | otherEdgeRows >> 7 | otherEdgeRows << 7 | otherEdgeRows >> 9 | otherEdgeRows << 9);
            UInt64 moveableRows = board.moveableRows;
            UInt64 otherMoveableRows = board.otherMoveableRows;
            int sideScore = (CountBit(otherEdgeRows & CornerFlag) - CountBit(selfEdgeRows & CornerFlag)) * 32
                + (CountBit(otherMoveableRows & InCornerFlag) - CountBit(moveableRows & InCornerFlag)) * 2
                + (pointCounts[otherRows & 0x81] + pointCounts[otherRows >> 56 & 0x81] - pointCounts[selfRows & 0x81] - pointCounts[selfRows >> 56 & 0x81]) * 64
                + (GetScore((byte)selfRows, (byte)otherRows) + GetScore((byte)(selfRows >> 56), (byte)(otherRows >> 56)) + GetScore(rowMaps[selfRows & VerticalFlag], rowMaps[otherRows & VerticalFlag]) + GetScore(rowMaps[selfRows >> 7 & VerticalFlag], rowMaps[otherRows >> 7 & VerticalFlag]));
            sideScore = sideScore * (CountBit(emptyRows) + 8) / 128;
            int score = (board.MoveableCount - board.OtherMoveableCount + CountBit(otherEdgeRows) - CountBit(selfEdgeRows) + (CountBit(edgeRows & otherRows) - CountBit(edgeRows & selfRows)) * 2 + sideScore) / 4;
            using (StreamWriter tw = new StreamWriter("score.txt", true))
            {
                for (int i = 0; i < 8; i++)
                {
                    for (int j = 0; j < 8; j++)
                    {
                        if ((board.SelfRows >> (i * 8 + j) & 1) == 1) tw.Write("o");
                        else if ((board.OtherRows >> (i * 8 + j) & 1) == 1) tw.Write("x");
                        else tw.Write("_");
                    }
                    tw.WriteLine();
                }
                tw.WriteLine("Score:{0} SideScore:{1} EdgeScore:{2} MoveableScore:{3}", score, sideScore, (CountBit(otherEdgeRows) - CountBit(selfEdgeRows) + CountBit(edgeRows & otherRows) - CountBit(edgeRows & selfRows)), board.MoveableCount - board.OtherMoveableCount);
                tw.Flush();
            }
        }

        public static int CalScore(byte self, byte other)
        {
            int allPoints = self | other;
            if (pointCounts[allPoints] == Board.Size)
                return (pointCounts[self] - pointCounts[other] + (pointCounts[self & 0x81] - pointCounts[other & 0x81]) * 2) * 16;
            else
            {
                byte selfMoveable = GetMoveablePlaces(self, other);
                byte otherMoveable = GetMoveablePlaces(other, self);
                int selfScore = 0, otherScore = 0;

                for (int i = 0; i < Board.Size; i++)
                {
                    if ((allPoints >> i & 1) == 0)
                    {
                        selfScore += -CalNextScore(self, other, i);
                        otherScore += CalNextScore(other, self, i);
                    }
                }

                selfScore /= Board.Size - pointCounts[allPoints];
                otherScore /= Board.Size - pointCounts[allPoints];

                for (int i = 0; i < Board.Size; i++)
                {
                    if ((selfMoveable >> i & 1) != 0) selfScore = Math.Max(selfScore, -CalNextScore(self, other, i));
                    if ((otherMoveable >> i & 1) != 0) otherScore = Math.Max(otherScore, CalNextScore(other, self, i));
                }

                if (selfMoveable != 0 && otherMoveable == 0) return (Math.Max(selfScore, otherScore) * 3 + Math.Min(selfScore, otherScore)) / 4;
                else if (selfMoveable == 0 && otherMoveable != 0) return (Math.Max(selfScore, otherScore) + Math.Min(selfScore, otherScore) * 3) / 4;
                else return (selfScore + otherScore) / 2;
            }
        }

        private static int CalNextScore(byte self, byte other, int i)
        {
            PutDown(ref self, ref other, i);
            return GetScore(other, self);
        }

        static StreamWriter tw = new StreamWriter("lib.txt", true);

        public static void Save(Board board)
        {
            for (int i = 0; i < 8; i++)
            {
                for (int j = 0; j < 8; j++)
                {
                    if ((board.SelfRows >> (i * 8 + j) & 1) == 1) tw.Write("o");
                    else if ((board.OtherRows >> (i * 8 + j) & 1) == 1) tw.Write("x");
                    else tw.Write("_");
                }
                tw.WriteLine();
            }
        }
    }
}
